Shortest path to get all keys [ Brute Force, Dijkstra’s algorithm]¶
Time: O(KxRxC + K3x2K); Space: O(Kx2^K); hard
We are given a 2-dimensional grid. “.” is an empty cell, “#” is a wall, “@” is the starting point, (“a”, “b”, …) are keys, and (“A”, “B”, …) are locks.
We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions. We cannot walk outside the grid, or walk into a wall. If we walk over a key, we pick it up. We can’t walk over a lock unless we have the corresponding key.
For some 1 <= K <= 6, there is exactly one lowercase and one uppercase letter of the first K letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.
Return the lowest number of moves to acquire all keys. If it’s impossible, return -1.
Example 1:
Input: grid =
["@.a.#",
"###.#",
"b.A.B"]
Output: 8
Example 2:
Input: grid =
["@..aA",
"..B#.",
"....b"]
Output: 6
Notes:
1 <= len(grid) <= 30
1 <= len(grid[0]) <= 30
grid[i][j] contains only ‘.’, ‘#’, ‘@’, ‘a’-‘f’ and ‘A’-‘F’
The number of keys is in [1, 6]. Each key has a different letter and opens exactly one lock.
1. Brute Force + Permutations¶
Intuition and Algorithm We have to pick up the keys K in some order, Kσi. For each ordering, let’s do a breadth first search to find the distance to the next key. For example, if the keys are ‘abcdef’, then for each ordering such as ‘bafedc’, we will try to calculate the candidate distance from ‘@’ -> ‘b’ -> ‘a’ -> ‘f’ -> ‘e’ -> ‘d’ -> ‘c’.
Between each segment of our path (and corresponding breadth-first search), we should remember what keys we’ve picked up. Keys that are picked up become part of a mask that helps us identify what locks we are allowed to walk through during the next breadth-first search.
Each part of the algorithm is relatively straightforward, but the implementation in total can be quite challenging. See the comments for more details.
[7]:
import collections
import itertools
class Solution1(object):
"""
Time: O(R∗C∗A∗A!), where R, C are the dimensions of the grid, and A is the maximum number of keys
(A because it is the "size of the alphabet".) Each BFS is performed up to A∗A! times.
Space: O(R*C + A!), the space for the bfs and to store the candidate key permutations.
"""
def shortestPathAllKeys(self, grid):
"""
:type grid: List[str]
:rtype: int
"""
R, C = len(grid), len(grid[0])
# location['a'] = the coordinates of 'a' on the grid, etc.
location = {v: (r, c)
for r, row in enumerate(grid)
for c, v in enumerate(row)
if v not in '.#'}
def neighbors(r, c):
for cr, cc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):
if 0 <= cr < R and 0 <= cc < C:
yield cr, cc
def bfs(source, target, keys = ()):
sr, sc = location[source]
tr, tc = location[target]
seen = [[False] * C for _ in range(R)]
seen[sr][sc] = True
queue = collections.deque([(sr, sc, 0)])
while queue:
r, c, d = queue.popleft()
if r == tr and c == tc:
return d
for cr, cc in neighbors(r, c):
if not seen[cr][cc] and grid[cr][cc] != '#':
if grid[cr][cc].isupper() and grid[cr][cc].lower() not in keys:
continue
queue.append((cr,cc,d+1))
seen[cr][cc] = True
return float('inf')
ans = float('inf')
keys = "".join(chr(ord('a') + i) for i in range(len(location) // 2))
for cand in itertools.permutations(keys):
# bns : the built candidate answer, consisting of the sum
# of distances of the segments from '@' to cand[0] to cand[1] etc.
bns = 0
for i, target in enumerate(cand):
source = cand[i-1] if i > 0 else '@'
d = bfs(source, target, cand[:i])
bns += d
if bns >= ans:
break
else:
ans = bns
return ans if ans < float('inf') else -1
[8]:
s = Solution1()
grid = [
"@.a.#",
"###.#",
"b.A.B"]
assert s.shortestPathAllKeys(grid) == 8
grid = [
"@..aA",
"..B#.",
"....b"]
assert s.shortestPathAllKeys(grid) == 6
2. Points of Interest + Dijkstra¶
Intuition and Algorithm
Clearly, we only really care about walking between points of interest: the keys, locks, and starting position. We can use this insight to speed up our calculation.
Let’s make this intuition more formal: any walk can be decomposed into primitive segments, where each segment (between two points of interest) is primitive if and only if it doesn’t touch any other point of interest in between.
Then, we can calculate the distance (of a primitive segment) between any two points of interest, using a breadth first search (BFS).
Afterwards, we have some graph (where each node refers to at most 13 places, and at most 2^6 states of keys). We have a starting node (at ‘@’ with no keys) and ending nodes (at anywhere with all keys.) We also know all the costs to go from one node to another - each node has outdegree at most 13. This shortest path problem is now ideal for using Dijkstra’s algorithm.
Dijkstra’s algorithm uses a priority queue to continually searches the path with the lowest cost to destination, so that when we reach the target, we know it must have been through the lowest cost path. Refer to this link for more detail.
Again, each part of the algorithm is relatively straightforward (for those familiar with BFS and Dijkstra’s algorithm), but the implementation in total can be quite challenging.
[11]:
import collections
import heapq
class Solution2(object):
"""
Time: O(RC(2A+1)+ElogN), where R, C are the dimensions of the grid,
and A is the maximum number of keys, N=(2A+1)∗2^A is the number of nodes when we perform Dijkstra's,
and E = N∗(2A+1) is the maximum number of edges.
Space: O(N).
"""
def shortestPathAllKeys(self, grid):
"""
:type grid: List[str]
:rtype: int
"""
R, C = len(grid), len(grid[0])
# The points of interest
location = {v: (r, c)
for r, row in enumerate(grid)
for c, v in enumerate(row)
if v not in '.#'}
def neighbors(r, c):
for cr, cc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):
if 0 <= cr < R and 0 <= cc < C:
yield cr, cc
# The distance from source to each point of interest
def bfs_from(source):
r, c = location[source]
seen = [[False] * C for _ in range(R)]
seen[r][c] = True
queue = collections.deque([(r, c, 0)])
dist = {}
while queue:
r, c, d = queue.popleft()
if source != grid[r][c] != '.':
dist[grid[r][c]] = d
continue # Stop walking from here if we reach a point of interest
for cr, cc in neighbors(r, c):
if grid[cr][cc] != '#' and not seen[cr][cc]:
seen[cr][cc] = True
queue.append((cr, cc, d+1))
return dist
dists = {place: bfs_from(place) for place in location}
target_state = 2 ** sum(p.islower() for p in location) - 1
#Dijkstra
pq = [(0, '@', 0)]
final_dist = collections.defaultdict(lambda: float('inf'))
final_dist['@', 0] = 0
while pq:
d, place, state = heapq.heappop(pq)
if final_dist[place, state] < d: continue
if state == target_state: return d
for destination, d2 in dists[place].items():
state2 = state
if destination.islower(): #key
state2 |= (1 << (ord(destination) - ord('a')))
elif destination.isupper(): #lock
if not(state & (1 << (ord(destination) - ord('A')))): #no key
continue
if d + d2 < final_dist[destination, state2]:
final_dist[destination, state2] = d + d2
heapq.heappush(pq, (d+d2, destination, state2))
return -1
[12]:
s = Solution2()
grid = [
"@.a.#",
"###.#",
"b.A.B"]
assert s.shortestPathAllKeys(grid) == 8
grid = [
"@..aA",
"..B#.",
"....b"]
assert s.shortestPathAllKeys(grid) == 6
[17]:
import collections
import heapq
class Solution3(object):
"""
Time: O(k*r*c + |E|log|V|) = O(k*r*c + (k*|V|)*log|V|)
= O(k*r*c + (k*(k*2^k))*log(k*2^k))
= O(k*r*c + (k*(k*2^k))*(logk + k*log2))
= O(k*r*c + (k*(k*2^k))*k)
= O(k*r*c + k^3*2^k)
Space: O(|V|) = O(k*2^k)
"""
def shortestPathAllKeys(self, grid):
"""
:type grid: List[str]
:rtype: int
"""
directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
def bfs(grid, source, locations):
r, c = locations[source]
lookup = [[False]*(len(grid[0])) for _ in range(len(grid))]
lookup[r][c] = True
q = collections.deque([(r, c, 0)])
dist = {}
while q:
r, c, d = q.popleft()
if source != grid[r][c] != '.':
dist[grid[r][c]] = d
continue
for direction in directions:
cr, cc = r + direction[0], c + direction[1]
if not ((0 <= cr < len(grid)) and
(0 <= cc < len(grid[cr]))):
continue
if grid[cr][cc] != '#' and not lookup[cr][cc]:
lookup[cr][cc] = True
q.append((cr, cc, d+1))
return dist
locations = {place: (r, c)
for r, row in enumerate(grid)
for c, place in enumerate(row)
if place not in '.#'}
dists = {place: bfs(grid, place, locations) for place in locations}
# Dijkstra's algorithm
min_heap = [(0, '@', 0)]
best = collections.defaultdict(lambda: collections.defaultdict(
lambda: float("inf")))
best['@'][0] = 0
target_state = 2**sum(place.islower() for place in locations)-1
while min_heap:
cur_d, place, state = heapq.heappop(min_heap)
if best[place][state] < cur_d:
continue
if state == target_state:
return cur_d
for dest, d in dists[place].items():
next_state = state
if dest.islower():
next_state |= (1 << (ord(dest)-ord('a')))
elif dest.isupper():
if not (state & (1 << (ord(dest)-ord('A')))):
continue
if cur_d+d < best[dest][next_state]:
best[dest][next_state] = cur_d+d
heapq.heappush(min_heap, (cur_d+d, dest, next_state))
return -1
[18]:
s = Solution3()
grid = [
"@.a.#",
"###.#",
"b.A.B"]
assert s.shortestPathAllKeys(grid) == 8
grid = [
"@..aA",
"..B#.",
"....b"]
assert s.shortestPathAllKeys(grid) == 6